package ch1.part3;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

/**
 * 第一章第三小节《以数组内查重问题演示空间复杂度》
 *
 * @author liuwanxiang
 * @version 2019/05/13
 */
public class SpaceComplexity {

    /**
     * 不使用散列表保存数据
     * 空间复杂度 O(n)=1
     * 时间复杂度 O(n)=n^2
     *
     * @param array
     */
    static void find1(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] == array[j]) {
                    System.out.printf("重复数为 %s\n", array[i]);
                    return;
                }
            }
        }
    }

    /**
     * 使用散列表保存字典数据
     * 空间复杂度 O(n)=n
     * 时间复杂度 O(n)=n
     *
     * @param array
     */
    static void find2(int[] array) {
        HashSet<Integer> set = new HashSet<Integer>();
        int size = set.size();
        for (int i = 0; i < array.length; i++) {
            set.add(array[i]);
            if (set.size() == size) {
                System.out.printf("重复数为 %s\n", array[i]);
                return;
            }
            size = set.size();
        }
    }

    public static void main(String[] args) {
        int[] array = {3, 1, 2, 5, 4, 9, 7, 2};
        find1(array);
        find2(array);
    }

}
